#include "WorldMap.h"
#include "perlinNoise.h"
#include "aStar.h"
#include "TextDrawer.h"

void WorldMap::generateTerrain(){
	fprintf(stderr, "> Terrain generation\n");
	// clear terrain data
	for(int i=0; i<_tilesX; i++)
		for(int j=0; j<_tilesY; j++){
			if(getLower(i,j) == OCEAN || getLower(i,j) == LAKE || getLower(i,j) == COAST) setUpper(i,j,OCCUPIED);
			else setUpper(i,j,EMPTY);
		}

	generateRivers();
	generateBridges();
	generateTreesAndMoutains();
	generateCities();

	// clear unused bridges and fix coasts terrain
	for(int x=0; x<_tilesX; x++)
	for(int y=0; y<_tilesY; y++)
	{
		if(getUpper(x,y) == BRIDGE)
		{
			int d;
			int c = 0;
			int tr;
			for(d=0; d<4; d++){
				tr = getUpper(x+dir[d][0],y+dir[d][1]);
				if(tr == ROAD || tr == CITY) c++;
			}
			if(c!=2) setUpper(x,y,RIVER);
		}
		if(getLower(x,y) == COAST && getUpper(x,y) == OCCUPIED)
			setUpper(x,y,EMPTY);
	}
}

void WorldMap::generateRivers(){
	fprintf(stderr, "  - Rivers\n");
	int sx, sy, osx, osy;
	vector<Node> rivers;

	// 1. Calculate number of rivers
	const int riverCount = _tilesX*_tilesY*0.001;

	int counter = 0;
	for(int r=0; r<riverCount; r++){
		// 2. Find a place to start the river, only at unoccupied high elevation land
		int t;
		do{
			osx = sx = rand()%_tilesX;
			osx = sy = rand()%_tilesY;
			t = getLower(sx,sy);
			counter++;
		} while(!(getUpper(sx,sy) == EMPTY && (t == POLAR || t == SCLEROPHYLL || t == STEPPE)) && counter < 100);
		if(counter == 100) break;
		else counter = 0;

		// 2.5. Surround it with mountains with p=0.75
		for(int d=0; d<12; d++) if(rand()%4 > 0){
			if(getUpper(sx+dir_star[d][0],sy+dir_star[d][1]) != RIVER)
				setUpper(sx+dir_star[d][0],sy+dir_star[d][1],MOUNTAIN);
		}
		setUpper(sx,sy,MOUNTAIN);

		// 3. Calculate the direction
		int p = rand()%61+20;
		bool bH = rand()%2;
		bool bV = rand()%2;

		// 4. Draw the river
		bool broke = false;
		while(!broke){
			osx = sx;
			osy = sy;

			// 4.1 Choose next river tile at random with direction probability
			if(rand()%100+1 > p) bH ? sy-- : sy++;
			else bV ? sx++ : sx--;

			// 4.2 Place the river tile if it's a proper position
			if(!(getLower(sx,sy) == OCEAN || getLower(sx,sy) == LAKE)){
				setUpper(sx,sy,RIVER);
				Node n = {sx,sy};
				rivers.push_back(n);
			}
			for(int d=0; d<4; d++){
				if(sx+dir[d][0] == osx && sy+dir[d][1] == osy) continue;
				int t = getLower(sx+dir[d][0],sy+dir[d][1]);
				// 4.3 Check if there's no river end
				if(t == OCEAN || t == NONE || t == LAKE || getUpper(sx+dir[d][0],sy+dir[d][1]) == RIVER){
					if(t == OCEAN || t == LAKE) setUpper(sx+dir[d][0],sy+dir[d][1],CONFLUENCE);
					broke = true;
					break;
				}
			}
		}
	}

	// ...delete river loops...
	bool broke = false;
	while(!broke){
		broke = true;
		for(unsigned int i=0; i<rivers.size(); i++){
			int x = rivers[i].x;
			int y = rivers[i].y;
			if(getUpper(x,y) == RIVER){
				int rdir[4][2] = {{0,0},{1,0},{0,1},{1,1}};
				int d;
				for(d=1; d<4; d++) if(getUpper(x+rdir[d][0],y+rdir[d][1]) != RIVER) break;
				if(d==4){ // If there's a river square
					for(d=0; d<4; d++){
						int nx = x+rdir[d][0];
						int ny = y+rdir[d][1];
						int counter = 0;
						for(int dr=0; dr<4; dr++){
							if(getUpper(nx+dir[dr][0],ny+dir[dr][1]) == RIVER
							|| getUpper(nx+dir[dr][0],ny+dir[dr][1]) == BRIDGE
							|| getUpper(nx+dir[dr][0],ny+dir[dr][1]) == CONFLUENCE
							) counter++;
						}
						if(counter == 2){
							setUpper(nx,ny,EMPTY);
							broke = false;
							break;
						}
					}
				}
			}
		}
	}
}

void WorldMap::generateBridges(){
	for(int x=0; x<_tilesX; x++)
		for(int y=0; y<_tilesY; y++){
			if(getUpper(x-1,y) == RIVER && getUpper(x+1,y) == RIVER && getUpper(x,y-1) != RIVER && getUpper(x,y+1) != RIVER)
				setUpper(x,y,BRIDGE);
			else if(getUpper(x-1,y) != RIVER && getUpper(x+1,y) != RIVER && getUpper(x,y-1) == RIVER && getUpper(x,y+1) == RIVER)
				setUpper(x,y,BRIDGE);
		}
}

void WorldMap::generateTreesAndMoutains(){
	fprintf(stderr, "  - Trees and moutains\n");
	ALLEGRO_BITMAP* flora = getPerlinNoise(_tilesX,_tilesY,20,0.3);
	ALLEGRO_BITMAP* terra = getPerlinNoise(_tilesX,_tilesY,20,0.3);
	//al_draw_bitmap(flora,10,_tilesY+20,0);
	//al_draw_bitmap(terra,20+_tilesX,_tilesY+20,0);
	//al_flip_display();
	al_lock_bitmap(flora,ALLEGRO_PIXEL_FORMAT_ANY,ALLEGRO_LOCK_READWRITE);
	al_lock_bitmap(terra,ALLEGRO_PIXEL_FORMAT_ANY,ALLEGRO_LOCK_READWRITE);
	for(int i=0; i<_tilesX; i++)
		for(int j=0; j<_tilesY; j++){
			int t = getLower(i,j);

			// Mountains
			if(getPixel(terra,i,j) > rand()%256){
				if(t != OCEAN && t != LAKE && t != COAST && getUpper(i,j) == EMPTY){
						if(rand()%5 == 0) setUpper(i,j,MOUNTAIN);
				}
			}

			// Trees
			if(getPixel(flora,i,j) > rand()%256){
				if(t != OCEAN && t != LAKE && t != COAST && getUpper(i,j) == EMPTY){
					int prob = 1;
					switch(t){
					case TROPIC: prob = 1; break;
					case FOREST: prob = 1; break;
					case SCLEROPHYLL: prob = 1; break;
					case SAVANNA: prob = 2; break;
					case DESERT: prob = 3; break;
					case STEPPE: prob = 4; break;
					case TAIGA: prob = 2; break;
					case TUNDRA: prob = 3; break;
					case POLAR: prob = 4; break;
					}
					if(rand()%4+1 >= prob) 
						if(rand()%3 >= 1) 
							setUpper(i,j,TREE);
				}
			}
		}

	al_unlock_bitmap(flora);
	al_destroy_bitmap(flora);
	al_unlock_bitmap(terra);
	al_destroy_bitmap(terra);
}

void WorldMap::generateCities(){
	fprintf(stderr, "  - Cities\n      ");

	// NodeData array for A* algorithm
	NodeData** Map = new NodeData*[_tilesX];
	for(int i=0; i<_tilesX; i++){
		Map[i] = new NodeData[_tilesY];
		for(int j=0; j<_tilesY; j++){
			int t = getLower(i,j);
			int tr = getUpper(i,j);
			Map[i][j].passable = (t != OCEAN && t != LAKE && tr != RIVER && tr != MOUNTAIN) ? true : false;
			Map[i][j].px = i;
			Map[i][j].py = j;
			Map[i][j].G = 0;
			Map[i][j].F = 0;
			Map[i][j].H = 0;
		}
	}

	// Main variables
	unsigned int cityCount = rand()%11+10; // !!! >= 2 (10-20)
	vector<Node> cities;
	vector<Node> routes;
	vector<Node> route;
	int cityDistance = 10;

	// Generate 2 initial cities and a road connecting them
	{
		cityDistance *= 3;
		Node start;
		Node end = findSettlement();
		while(true){
			start = end;
			end = findSettlement();

			double dist = sqrt((double)((start.x-end.x)*(start.x-end.x)+(start.y-end.y)*(start.y-end.y)));
			if(dist < cityDistance) continue;

			routes.clear();
			routes.push_back(end);
			route = aStarSearch(Map,_tilesX,_tilesY,start,routes);
			if(route.empty()) continue;

			cities.push_back(start);
			cities.push_back(end);
			routes.push_back(start);
			fprintf(stderr, "\r      Initial 0:(%d,%d) 1:(%d,%d)\n",start.x,start.y,end.x,end.y);
			break;
		}

		for(unsigned int i=0; i<route.size(); i++){
			routes.push_back(route[i]);
		}

		cityDistance /= 3;
	}

	// Generate the rest of the cities
	{
		ALLEGRO_BITMAP* disp = al_get_target_bitmap();
		ALLEGRO_BITMAP* borders = al_create_bitmap(_tilesX,_tilesY);
		al_set_target_bitmap(borders);
		al_clear_to_color(al_map_rgb(255,255,255));
		al_draw_filled_circle(cities[0].x,cities[0].y,cityDistance,al_map_rgb(0,0,0));
		al_draw_filled_circle(cities[1].x,cities[1].y,cityDistance,al_map_rgb(0,0,0));

		int counter = 0;
		while(cities.size() < cityCount && counter < 20){
			counter++;
			fprintf(stderr, "\r      Rest %d/%d cities ",cities.size()+1,cityCount);
			Node newCity = findSettlement();
			if(getPixel(borders,newCity.x,newCity.y) != 255) continue;

			//al_set_target_bitmap(disp);
			//al_draw_bitmap(borders,10,30+2*_tilesY,0);
			//al_set_target_bitmap(borders);
			//al_flip_display();

			route = aStarSearch(Map,_tilesX,_tilesY,newCity,routes);
			if(route.empty()){
				for(int i=0; i<_tilesX; i++)
					for(int j=0; j<_tilesY; j++)
						if(getLower(i,j) == OCEAN) Map[i][j].passable = true;
				route = aStarSearch(Map,_tilesX,_tilesY,newCity,routes);
				for(int i=0; i<_tilesX; i++)
						for(int j=0; j<_tilesY; j++)
							if(getLower(i,j) == OCEAN) Map[i][j].passable = false;
				if(route.empty()) continue;
			}

			cities.push_back(newCity);
			al_draw_filled_circle(newCity.x,newCity.y,cityDistance,al_map_rgb(0,0,0));
			for(unsigned int i=0; i<route.size(); i++){
				routes.push_back(route[i]);
			}
			counter = 0;
		}
		al_set_target_bitmap(disp);
		al_destroy_bitmap(borders);
	}

	// Place the cities
	for(unsigned int i=0; i<cities.size(); i++){
		int x = cities[i].x;
		int y = cities[i].y;
		setUpper(x,y,CITY);
	}

	placeRoads(routes);

	for(int i=0; i<_tilesX; i++) delete[] Map[i];
	delete[] Map;
}

Node WorldMap::findSettlement(){
	Node n;
	int t;
	int tr;
	do{
		n.x = rand()%_tilesX;
		n.y = rand()%_tilesY;
		t = getLower(n.x,n.y);
		tr = getUpper(n.x,n.y);
	} while(t == OCEAN || t == LAKE || t == COAST || tr == RIVER || tr == BRIDGE
		   || n.x == 0 || n.y == 0 || n.x == _tilesX-1 || n.y == _tilesY-1);

	return n;
}

void WorldMap::placeRoads(vector<Node> aRoads){
	fprintf(stderr, "\n  - Roads    \n");

	// Place the roads...
	for(unsigned int i=0; i<aRoads.size(); i++){
		int x = aRoads[i].x;
		int y = aRoads[i].y;
		if(getLower(x,y) == OCEAN) setUpper(x,y,WROAD);
		else if(getUpper(x,y) != BRIDGE && getUpper(x,y) != CITY) setUpper(x,y,ROAD);
	}
	// ...find a place for ports...
	for(unsigned int i=0; i<aRoads.size(); i++){
		int x = aRoads[i].x;
		int y = aRoads[i].y;
		if(getLower(x,y) == OCEAN){
			for(int d=0; d<4; d++)
				if(getLower(x+dir[d][0],y+dir[d][1]) == COAST && getUpper(x+dir[d][0],y+dir[d][1]) == ROAD)
					setUpper(x,y,PORT);
					//for(int dr=0; dr<4; dr++)
					//	if(getLower(x+dir[dr][0],y+dir[dr][1]) != OCEAN && getUpper(x+dir[dr][0],y+dir[dr][1]) == ROAD)
					//		setUpper(x,y,PORT);
		}
	}
	// ...delete road loops...
	bool broke = false;
	while(!broke){
		broke = true;
		for(unsigned int i=0; i<aRoads.size(); i++){
			int x = aRoads[i].x;
			int y = aRoads[i].y;
			if(getUpper(x,y) == ROAD){
				int rdir[4][2] = {{0,0},{1,0},{0,1},{1,1}};
				int d;
				for(d=1; d<4; d++) if(getUpper(x+rdir[d][0],y+rdir[d][1]) != ROAD) break;
				if(d==4){ // If there's a road square
					for(d=0; d<4; d++){
						int nx = x+rdir[d][0];
						int ny = y+rdir[d][1];
						int counter = 0;
						for(int dr=0; dr<4; dr++){
							if(getUpper(nx+dir[dr][0],ny+dir[dr][1]) == ROAD
							|| getUpper(nx+dir[dr][0],ny+dir[dr][1]) == CITY
							|| getUpper(nx+dir[dr][0],ny+dir[dr][1]) == BRIDGE) counter++;
						}
						if(counter == 2){
							setUpper(nx,ny,EMPTY);
							broke = false;
							break;
						}
					}
				}
			}
		}
	}
	// ...and dead ends
	for(int i=0; i<_tilesX; i++)
		for(int j=0; j<_tilesY; j++){
			if(getUpper(i,j) == ROAD){
				int nodes = 0;
				for(int d=0; d<4; d++){
					int tr = getUpper(i+dir[d][0],j+dir[d][1]);
					if(tr == ROAD || tr == PORT || tr == BRIDGE || tr == CITY) nodes++;
				}
				if(nodes < 2){
					setUpper(i,j,EMPTY);
					i=0;
					j=0;
				}
			}
		}
}